/*
https://leetcode-cn.com/problems/smallest-rotation-with-highest-score/solution/de-fen-zui-gao-de-zui-xiao-lun-diao-by-l-hbtd/
 */
public class Solution798 {
    public int bestRotation(int[] nums) {
        int[] f=new int[nums.length+1];
        for (int i=0;i<nums.length;i++){
            if (nums[i]>i){
                f[i+1]++;
                f[nums.length-nums[i]+i+1]--;
            }else{
                f[0]++;
                f[i-nums[i]+1]--;
                f[i+1]++;
                f[nums.length]--;
            }
        }
        int cur=0;
        int max=-1;
        int ans=-1;
        for (int i=0;i<nums.length;i++){
            cur+=f[i];
            if (cur>max){
                max=cur;
                ans=i;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution798().bestRotation(new int[]{2,3,1,4,0}));
    }
}
